package com.LeeCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 将一个数字表示成幂的和的方案数
 */

public class Code2787 {
    public static void main(String[] args) {
        int n = 4, x = 1;
        System.out.println(new Code2787().numberOfWays(n, x));
    }

    public int numberOfWays(int n, int x) {
        final int MOD = 1000000007;

        // 生成所有不超过n的x次幂
        List<Long> powers = new ArrayList<>();
        for (int i = 1; ; i++) {
            long power = (long) Math.pow(i, x);
            if (power > n) break;
            powers.add(power);
        }

        // dp[i] 表示和为i的方案数
        int[] dp = new int[n + 1];
        dp[0] = 1; // 和为0的方案数为1（空集合）

        // 对每个x次幂进行0-1背包
        for (long power : powers) {
            int p = (int) power;
            // 从后往前更新，避免重复使用同一个数
            for (int i = n; i >= p; i--) {
                dp[i] = (dp[i] + dp[i - p]) % MOD;
            }
        }

        return dp[n];
    }
}
